package com.lh.nk;

/**
 * @author: linghao
 * @since: 2023/2/2
 *
 * 描述
 * 将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
 * 如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
 * 你不能更改节点中的值，只能更改节点本身
 *
 *
{1,2,3,4,5},2
{2,1,4,3,5}
 */
public class 链表中的节点每k个一组翻转NC50 {

    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        ListNode tail = head;
        //将tail指针移到组的末尾
        for(int i=0;i<k;i++){
            if(tail == null)return head;
            tail = tail.next;
        }

        ListNode pre = null;
        ListNode cur = head;
        //反转分段的链表
        while (cur != tail){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        //当前尾部指向下一个要反转的链表段,因为当前head经过上面的反转操作已经变为链表段的尾部
        head.next = reverseKGroup(tail,k);
        return pre;
    }



    class ListNode {
        int val;
        ListNode next = null;
    }
}

